package com.FindAnd_Replace_in_String;

public class Solution {
	public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
		int length = indexes.length;
		StringBuffer s = new StringBuffer(S);
		//s.insert
		for(int i=0;i<length;i++) {
			int index=indexes[i];
			if(index<0){
                continue;
            }
			String source=sources[i];
			String target = targets[i];
			int end=findSameString(source, index, new String(s));
			if(end==-1)continue;
			else {
				s.replace(index, end, target);
				if(i+1<length) {
					//说明后面还有要替换掉那么将index进行修改
					int oldlength=end-index;//原来的数组中药替换的长度
					int newlength=target.length();//现在新的替换的长度
					int change=newlength-oldlength;
					//凡是后面数组中大于此index的都要改,小于此index的不需要改
					for(int j=i+1;j<length;j++) {
						if(indexes[j]>=index) {
							indexes[j]=indexes[j]+change;
						}
					}
				}
			}
		}
		S = new String(s);
		return S;
	}
	public int findSameString(String source,int index,String S) {
		char t1[]=source.toCharArray();
		char t2[]=S.toCharArray();
		int j=index;
		if(index>=S.length()) {
			return -1;
		}
		for(int i=0;i<t1.length;i++) {
		   	if(j<S.length()&&t1[i]==t2[j]) {
		   		j++;
		   	}
		   	else {
		   		return -1;
		   	}
		
		}
		return j;
	}
}
